public class MaxSubarraySum {

    public static void main(String[] args) {
        // 第二题所给测试样例
        int[] arr1 = {1, -2, 3, 5, -1};
        int[] arr2 = {1, -2, 3, -8, 5, 1};
        int[] arr3 = {1, -2, 3, -2, 5, 1};

        System.out.println(maxSubarraySum(arr1));// 输出: 8
        System.out.println(maxSubarraySum(arr2));// 输出: 6
        System.out.println(maxSubarraySum(arr3));// 输出: 7
    }

        public static int maxSubarraySum(int[] arr) {
            if (arr.length == 0) {
                return 0;
            }

            // 将max1和max2据复制arr[0]
            int max1 = arr[0];
            int max2 = arr[0];
            // 遍历整个数组
            for (int i = 1; i < arr.length; i++) {
                //max1是记录以当前元素为结尾的子数组的最大和
                max1 = Math.max(arr[i], max1 + arr[i]);
                //max2是记录当前找到的所有子数组的做大和
                max2 = Math.max(max1,max2);
            }
            
            return max2;
        }
        
    }
